#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
//#include<boost/algorithm/string/classification.hpp>
//#include<boost/algorithm/string/split.hpp>
using namespace std;
//题目链接：https ://leetcode.cn/problems/number-of-islands
//二维向量赋值：https://blog.csdn.net/qq_43826212/article/details/104172731/

class Solution {
private:
    int dir[4][2] = { 0, 1, 1, 0, -1, 0, 0, -1 }; // 四个方向 // 4行2列的数组
    void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y)  //创建一个二维向量
    {
        for (int i = 0; i < 4; i++) 
        {
            int nextx = x + dir[i][0]; //列方向，上下移动
            int nexty = y + dir[i][1]; //行方向，左右移动
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过
            if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') { // 没有访问过的 同时 是陆地的

                visited[nextx][nexty] = true;
                dfs(grid, visited, nextx, nexty);
            }
        }
    }
public:
    int numIslands(vector<vector<char>>& grid) 
    {
        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    result++; // 遇到没访问过的陆地，+1
                    dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
                }
            }
        }
        return result;
    }
};

class Solution002 {
private:
    int dir[4][2] = { 0, 1, 1, 0, -1, 0, 0, -1 }; // 四个方向 // 4行2列的数组
    void dfs(vector<vector<char>>& grid, int x, int y)
    {
        for (int i = 0; i < 4; i++)
        {
            int nextx = x + dir[i][0]; //列方向，上下移动
            int nexty = y + dir[i][1]; //行方向，左右移动
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过
            if (grid[nextx][nexty] == '1') { // 没有访问过的 同时 是陆地的
                
                grid[nextx][nexty] = '0'; //已经统计过的位置清0
                dfs(grid, nextx, nexty);
            }
        }
    }
public:
    int numIslands(vector<vector<char>>& grid)
    {
        int n = grid.size(), m = grid[0].size();
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') {
                    result++; // 遇到没访问过的陆地，+1
                    dfs(grid, i, j); 
                }
            }
        }
        return result;
    }
};



int main() {
    vector<vector<char>> grid;
    grid.push_back({ '1','1','0','0','0' });
    grid.push_back({ '1','1','0','0','0' });
    grid.push_back({ '0','0','1','0','0' });
    grid.push_back({ '1','0','0','1','1' });

    Solution s1;
    int res = s1.numIslands(grid);
    cout << res << endl;

    Solution002 s2;
    res = s2.numIslands(grid);
    cout << res << endl;

    system("pause");
    return 0;
}










